package arithmetic;

import java.util.Stack;

/**
 * @Author: Jie
 * @Date: 2019/1/14 16:52
 * @Function : 用栈 实现队列  leetcode 232
 * https://leetcode-cn.com/problems/implement-queue-using-stacks/
 * <p>
 * 栈：
 * push(x) -- 元素 x 入栈
 * pop() -- 移除栈顶元素
 * peek() -- 获取栈顶元素
 * empty() -- 返回栈是否为空
 * <p>
 * TODO 队列：
 * 使用栈实现队列的下列操作：
 * push(x) -- 将一个元素放入队列的尾部。
 * pop() -- 从队列首部移除元素。
 * peek() -- 返回队列首部的元素。
 * empty() -- 返回队列是否为空。
 * eg:
 * MyQueue queue = new MyQueue();
 * queue.push(1);
 * queue.push(2);
 * queue.peek();  // 返回 1
 * queue.pop();   // 返回 1
 * queue.empty(); // 返回 false
 */
public class A_03_StackToQueue {
    public static void main(String[] args) {

        //已完成
        //执行用时: 92 ms
        //输入
        //["MyQueue","push","push","peek","pop","empty"]
        //[[],[1],[2],[],[],[]]
        //输出
        //[null,null,null,1,1,false]
        //差别
        //预期结果
        //[null,null,null,1,1,false]
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        System.out.println(myQueue.peek());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.empty());
    }
}

//91ms
class MyQueue {
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        inputStack.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (outputStack.isEmpty()) {
            if (!inputStack.isEmpty()) {
                while (!inputStack.isEmpty()) {
                    outputStack.push(inputStack.pop());
                }
                return outputStack.pop();
            }
        } else {
            return outputStack.pop();
        }
        return -1;
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (outputStack.isEmpty()) {
            if (!inputStack.isEmpty()) {
                while (!inputStack.isEmpty()) {
                    outputStack.push(inputStack.pop());
                }
                return outputStack.peek();
            }
        } else {
            return outputStack.peek();
        }
        return -1;
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
}

//56ms
class MyQueueFirst {
    Stack<Integer> in = null;
    Stack<Integer> out = null;
    public MyQueueFirst() {
        in = new Stack<>();
        out = new Stack<>();
    }
    public void push(int x) {
        in.push(x);
    }
    public int pop() {
        peek();
        return out.pop();
    }
    public int peek() {//不空的时候，直接查询返回即可
        if(out.isEmpty())//空的时候，再倒换stack
            while(!in.isEmpty())
                out.push(in.pop());
        return out.peek();
    }
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}




